/*
https://leetcode.cn/problems/single-element-in-a-sorted-array/description/
540. 有序数组中的单一元素
*/

class Solution {
public:
// 数组是有序的。
// 除了一个数出现一次外，其余每个数都出现两次。
// 第二个条件意味着，数组的长度一定是奇数。
// 第一个条件意味着，出现两次的数，必然相邻，不可能出现 1,2,1 这样的顺序。
// 这也意味着，只出现一次的那个数，一定位于偶数下标上。
    int singleNonDuplicate(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid = l + (r-l)/2;
// 对于下标x左边的下标 y，如果 nums[y]=nums[y+1]，则 y 一定是偶数；
// 对于下标x右边的下标 z，如果 nums[z]=nums[z+1]，则 z 一定是奇数。
// 偶 奇 x 奇 偶
// 当 mid 是偶数时，mid+1=mid^1；2+1==2^1
// 当 mid 是奇数时，mid−1=mid^1。3-1==3^1
            if(nums[mid]==nums[mid^1])
//如果奇 例nums[5]==nums[4] 说明正常,x在右边
//如果奇 例nums[5]!=nums[4] 说明不正常,left~5内存在x,改变了奇偶匹配下标
//如果偶 例nums[6]==nums[7] 说明正常,x在右边
//如果偶 例nums[6]!=nums[7] 说明不正常,left~6内存在x,改变了奇偶匹配下标
            {
                l=mid+1;
            }
            else
            r=mid;
        }
        return nums[l];
    }
};